import math
import random
def assign_cluster(x, centers):
    min_dist = float('inf')
    cluster_idx = 0
    for i, c in enumerate(centers):
        # 计算欧氏距离
        dist = math.sqrt(sum([(a - b) ** 2 for a, b in zip(x, c)]))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    return cluster_idx

def Kmeans(data, k, epsilon=1e-4, iteration=100):
    if k <= 0 or k > len(data):
        raise ValueError("k值必须为正且不大于样本数量")
    if len(data) == 0:
        raise ValueError("数据集不能为空")
    # 初始化聚类中心
    n_samples = len(data)
    n_features = len(data[0])
    centers_idx = random.sample(range(n_samples), k)
    centers = [data[i] for i in centers_idx]

    for _ in range(iteration):
        # 分配每个样本到最近的聚类中心
        clusters = [[] for _ in range(k)]  # 存储每个聚类的样本索引
        for i, x in enumerate(data):
            c_idx = assign_cluster(x, centers)
            clusters[c_idx].append(i)

        # 计算新的聚类中心
        new_centers = []
        for cluster in clusters:
            if not cluster:  # 防止空聚类
                new_center = data[random.randint(0, n_samples - 1)]
            else:
                # 计算每个特征的均值
                new_center = []
                for j in range(n_features):
                    mean_val = sum([data[i][j] for i in cluster]) / len(cluster)
                    new_center.append(mean_val)
            new_centers.append(new_center)

        # 检查是否收敛（所有中心变化都小于epsilon）
        center_changes = [
            math.sqrt(sum([(a - b) ** 2 for a, b in zip(old, new)]))
            for old, new in zip(centers, new_centers)
        ]
        if max(center_changes) < epsilon:
            centers = new_centers
            break
        centers = new_centers
    return clusters, centers
#测试数据
if __name__ == "__main__":
    data = [
        [1, 2], [1, 4], [1, 0],
        [10, 2], [10, 4], [10, 0],
        [5, 5], [6, 6], [7, 7]
    ]

    # 聚类（k=3）
    clusters, centers = Kmeans(data, k=3, epsilon=1e-3, iteration=50)

    # 输出结果
    print("聚类中心：")
    for i, center in enumerate(centers):
        print(f"中心 {i + 1}: {center}")

    print("\n聚类结果：")
    for i, cluster in enumerate(clusters):
        print(f"聚类 {i + 1} 的样本：{[data[idx] for idx in cluster]}")